package com.kehao.leetcode.basic.string;


import org.junit.Test;

import java.util.Arrays;

public class StringSolution7 {

    //kmp算法实现
    public int strStr(String haystack, String needle) {
        if(needle.length()==0) return 0;
        if(haystack.length()==0) return -1;
        int[] next = getNextArray(needle);
        int i=0,j=0;
        while (i<haystack.length()&&j<needle.length()){
            if(haystack.charAt(i)==needle.charAt(j)){
                i++;
                j++;
            }else {
                if(next[j]==-1){
                    i++;
                }else {
                    j = next[j];
                }
            }
        }
        if(j==needle.length()) return i-needle.length();
        else return -1;
    }

    private int[] getNextArray(String needle) {
        int[] next = new int[needle.length()];
        next[0] = -1;
        int k = -1;
        for (int i = 0; i < needle.length()-1;) {
            if(k==-1||needle.charAt(i)==needle.charAt(k)){
                i++;
                k++;
                next[i] = k;
            }else {
                k = next[k];
            }
        }
        return next;
    }

    @Test
    public void myTest01(){
        int[] next = getNextArray("abaabcaba");
        Arrays.stream(next).forEach(i-> System.out.print(i));
    }

    @Test
    public void myTest02(){
        String haystack = "hello";
        String needle = "ll" ;
        System.out.println(strStr(haystack,needle));
    }

    @Test
    public void myTest03(){
        String haystack = "aaaaa";
        String needle = "bba" ;
        System.out.println(strStr(haystack,needle));
    }

    @Test
    public void myTest04(){
        String haystack = "a";
        String needle = "a" ;
        System.out.println(strStr(haystack,needle));
    }

    @Test
    public void myTest05(){
        String haystack = "mississippi";
        String needle = "issipi" ;
        System.out.println(strStr(haystack,needle));
    }
}
